package com.LeetCode.StackAndHeap;


/**
 * 索引堆
 */
public class IndexHeap {

    private int[] arr;
    private int[] index;
    private int count; // 元素数量
    private int capacity; // 容量

    public IndexHeap(int capacity){
        this.capacity = capacity;
        this.count = 0;
        arr = new int[capacity + 1];// 索引从 0 开始
        index = new int[capacity + 1];
    }

    public boolean isEmpty(){
        return  count == 0;
    }

    public int size(){
        return count;
    }

    public void insertItem(int item){
        if(count + 1 > capacity){
            return;
        }
        else{
            count++;
            arr[count] = item;
            index[count] = count;

            //从count开始向上调整
            shifDown(count);
        }
    }

    public void shiftUp(int k){
        if(k > 1 && arr[k/2] < arr[k]){
            int tmp = arr[k];
            arr[k] = arr[k/2];
            arr[k/2] = tmp;
        }else{
            return;
        }

        k /=2;
        shiftUp(k);
    }

    public void shifDown(int k){
        while(2 * k <= count){
            int j = 2 * k;
            if(j + 1 <= count && arr[index[j+1]]> arr[index[j]])
                j += 1;
            if(arr[index[j]] > arr[index[k]]){
                int tmp = index[j];
                index[j] = index[k];
                index[k] = tmp;

                k = j;
            }else{
                break;
            }

        }
    }

    public int pop(){
        if(count < 1){
            return -1;
        }else{
            int item = arr[index[1]];

            index[1] = index[count];
            count--;

            shiftUp(1);

            return item;
        }
    }

    public int peek(){
        return index[1];
    }

    public int getItemByIndex(int i){
        return arr[index[i]];
    }
}
